package medium;

/**
 *  * f[i,j] 表示i到j的字符串是否为回文子串，i始终大于j
 * 判断f[i,j]是否为回文子串只要判断f[i+1,j-1]&&s[i]==s[j]即可
 *    1如果i+1== j-1返回true；
 *    2如果i+1>j-1则判断s[i]==s[j]即可；
 *    3当i==j时，f[i,j]为true
 */
public class T5 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("aaaa"));
    }

    public static String longestPalindrome(String s) {

        int maxLen = 0;
        int indexI = 0;
        int indexJ = 0;
        Boolean[][] f = new Boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                boolean isPalindrome;
                if (f[i][j] != null) {
                    isPalindrome = f[i][j];
                } else {
                    isPalindrome = dp(s, i, j, f);
                }
                if (isPalindrome) {
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        indexI = i;
                        indexJ = j;
                        if (maxLen >= s.length()) {
                            return s.substring(indexI, indexJ + 1);
                        }
                    }
                }
            }
        }
        return s.substring(indexI, indexJ + 1);
    }

    // 判断f[i,j]是否为回文子串
    public static boolean dp(String s, int i, int j, Boolean[][] f) {
        if (i == j) {
            f[i][j] = true;
            return true;
        } else {
            if (i - j == -1) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = true;
                    return true;
                } else {
                    f[i][j] = false;
                    return false;
                }
            } else {
                if (i + 1 == j - 1) {
                    f[i + 1][j - 1] = true;
                }
                // 如果当前f[i+1][j-1]未计算过，则先计算
                if (f[i + 1][j - 1] == null) {
                    dp(s, i + 1, j - 1, f);
                }
                if (f[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                    f[i][j] = true;
                    return true;
                } else {
                    f[i][j] = false;
                    return false;
                }
            }
        }
    }
}
